package cn.zyf;

import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

public class Sudoku {

    public static void main(String[] args) {
        new Sudoku().run();
    }

    private void run() {
//        int[][] matrix = new int[][] {
//                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//        };
        int[][] matrix = new int[][] {
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 5, 0, 0, 7, 0, 0, 9, 0},
                {0, 0, 4, 0, 0, 0, 0, 0, 8, 6},
                {0, 8, 0, 0, 0, 1, 0, 0, 0, 0},
                {0, 0, 6, 0, 5, 4, 0, 2, 0, 0},
                {0, 0, 2, 0, 0, 0, 0, 0, 5, 9},
                {0, 0, 0, 4, 0, 3, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 1, 0, 0, 7},
                {0, 0, 0, 8, 4, 0, 0, 0, 0, 3},
                {0, 0, 0, 0, 7, 2, 9, 0, 0, 0},
        };
        copy(matrix, lastM);
        fill(matrix);
    }

    int[][] lastM = new int[10][10];
    private void copy(int[][] matrix, int[][] lastM) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                lastM[i][j] = matrix[i][j];
            }
        }
    }

    private static final Set<Integer> all = Collections.unmodifiableSet(new HashSet<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9)));

    private void fill(int[][] matrix) {
        Number[] numbers = init(matrix);
        int count = 0;
        while (true) {
            if (finish(matrix)) {
                System.out.println("success");
                print(matrix);
                return;
            }
            boolean renew = false;
            while (num(matrix, numbers)) {
                System.out.println(++count);
                renew = true;
                print(matrix);
            }
            for (int i = 1; i <= 9; i++) {
                for (int j = 1; j <= 9; j++) {
                    if (matrix[i][j] == 0) {
                        Set<Integer> remain = remain(matrix, i, j);
                        if (remain.size() == 1) {
                            for (int x : remain) {
                                matrix[i][j] = x;
                                syncNumber(numbers, i, j, x);
                                break;
                            }
                            System.out.println(++count);
                            renew = true;
                            print(matrix);
                        }
                    }
                }
            }
            if (!renew) {
                System.out.println("failed");
                print(matrix);
                return;
            }
        }
    }

    private boolean finish(int[][] matrix) {
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= 9; j++) {
                if (matrix[i][j] == 0) {
                    return false;
                }
            }
        }
        return true;
    }

    private void print(int[][] matrix) {
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= 9; j++) {
                if (matrix[i][j] == lastM[i][j]) {
                    System.out.print(matrix[i][j] + " ");
                } else {
                    System.out.print("\"" + matrix[i][j] + "\" ");
                }
            }
            System.out.println();
        }
        copy(matrix, lastM);
    }

    // 初始化1~9各数字的row和col索引
    private Number[] init(int[][] matrix) {
        Number[] numbers = new Number[10];
        for (int i = 1; i <= 9; i++) {
            numbers[i] = new Number();
        }
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= 9; j++) {
                if (matrix[i][j] != 0) {
                    Number number = numbers[matrix[i][j]];
                    number.rows[i] = j;
                    number.cols[j] = i;
                }
            }
        }
        return numbers;
    }

    // 每次matrix数据更新时同步更新row和col索引
    private void syncNumber(Number[] numbers, int row, int col, int value) {
        Number number = numbers[value];
        number.rows[row] = col;
        number.cols[col] = row;
    }

    // 判断每一个空位的横行、竖向、9宫格排除完后还能填几个数字
    private Set<Integer> remain(int[][] matrix, int row, int col) {
        Set<Integer> remain = new HashSet<>(all);
        for (int i = 1; i <= 9; i++) {
            if (matrix[i][col] != 0) {
                remain.remove(matrix[i][col]);
            }
        }
        for (int j = 1; j <= 9; j++) {
            if (matrix[row][j] != 0) {
                remain.remove(matrix[row][j]);
            }
        }
        int x = (row - 1) / 3 + 1;
        int y = (col - 1) / 3 + 1;
        int sx = (x - 1) * 3 + 1;
        int ex = x * 3;
        int sy = (y - 1) * 3 + 1;
        int ey = y * 3;
        for (int i = sx; i <= ex; i++) {
            for (int j = sy; j <= ey; j++) {
                if (matrix[i][j] != 0) {
                    remain.remove(matrix[i][j]);
                }
            }
        }
        return remain;
    }

    // 以1~9的单个数字为主，看是否能完全确定（单个数字在每一行、每一列只会出现一次，以及在9宫格内也指出出现一次）
    private boolean num(int[][] matrix, Number[] numbers) {
        // row direction
        for (int n = 1; n <= 9; n++) {
            Number number = numbers[n];
            int[] rows = number.rows;
            int[] cols = number.cols;
            int[] si = new int[] {1, 4, 7};
            int[] ei = new int[] {3, 6, 9};
            for (int block = 0; block < si.length; block++) {
                for (int i = si[block]; i <= ei[block]; i++) {
                    if (rows[i] == 0) {
                        Set<Integer> remain = new HashSet<>(all);
                        for (int oi = si[block]; oi <= ei[block]; oi++) {
                            if (oi != i && rows[oi] != 0) {
                                int y = (rows[oi] - 1) / 3 + 1;
                                int sy = (y - 1) * 3 + 1;
                                int ey = y * 3;
                                for (int j = sy; j <= ey; j++) {
                                    remain.remove(j);
                                }
                            }
                        }
                        for (int j = 1; j <= 9; j++) {
                            if (cols[j] != 0 || matrix[i][j] != 0) {
                                remain.remove(j);
                            }
                        }
                        if (remain.size() == 1) {
                            for (int x : remain) {
                                matrix[i][x] = n;
                                syncNumber(numbers, i, x, n);
                                break;
                            }
                            return true;
                        }
                    }
                }
            }
        }
        // col direction
        for (int n = 1; n <= 9; n++) {
            Number number = numbers[n];
            int[] rows = number.rows;
            int[] cols = number.cols;
            int[] sj = new int[] {1, 4, 7};
            int[] ej = new int[] {3, 6, 9};
            for (int block = 0; block < sj.length; block++) {
                for (int j = sj[block]; j <= ej[block]; j++) {
                    if (cols[j] == 0) {
                        Set<Integer> remain = new HashSet<>(all);
                        for (int oj = sj[block]; oj <= ej[block]; oj++) {
                            if (oj != j && cols[oj] != 0) {
                                int x = (cols[oj] - 1) / 3 + 1;
                                int sx = (x - 1) * 3 + 1;
                                int ex = x * 3;
                                for (int i = sx; i <= ex; i++) {
                                    remain.remove(i);
                                }
                            }
                        }
                        for (int i = 1; i <= 9; i++) {
                            if (rows[i] != 0 || matrix[i][j] != 0) {
                                remain.remove(i);
                            }
                        }
                        if (remain.size() == 1) {
                            for (int x : remain) {
                                matrix[x][j] = n;
                                syncNumber(numbers, x, j, n);
                                break;
                            }
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }

    private static class Number {
        int[] rows;
        int[] cols;

        Number() {
            this.rows = new int[10];
            Arrays.fill(this.rows, 0);
            this.cols = new int[10];
            Arrays.fill(this.cols, 0);
        }
    }

}
